package com.qisi.kandroidshalon.leetcode.sort;

import com.qisi.kandroidshalon.leetcode.Util;

public class SimpleSort {
    /**
     * 选择排序
     * 思路：
     * 每一次循环从找到最小值放到i位置，i从0开始
     */
    public static void selectSort(Integer[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            //交换
            Util.swap(array, minIndex, i);
            Util.dumpArray(array);
        }
    }

    public static void bubbleSort(Integer[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        for (int e = array.length - 1; e > 0; e--) {
            for (int i = 0; i < e; i++) {
                if (array[i] > array[i + 1]) {
                    Util.swap(array, i, i + 1);
                }
            }
            Util.dumpArray(array);
        }
    }

    /**
     * todo 多复习此排序思想
     * @param array
     */
    public static void insertSort(Integer[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        //0-[i-1]的范围已经排序了,j从后往前遍历，只要j+1比较小就往前交换
        for (int i = 1; i < array.length; i++) {
            for (int j = i - 1; j >= 0 && (array[j] > array[j + 1]); j--) {
                Util.swap(array, j, j + 1);
            }
            Util.dumpArray(array);
        }
    }


}
